package com.dmall.chapter03.section03;

/**
 * 加缓存的方式：自顶向下的递归
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 * @author xiao1.wang
 * @date 2020-12-01 10:54:21
 */
public class Leetcode70V2 {

    private int[] cache;

    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        cache = new int[n + 1];
        climbStair(n);
        return cache[n];
    }

    private int climbStair(int n) {
        if (n <= 2) {
            cache[n] = n;
            return cache[n];
        } else if (cache[n] != 0) {
            return cache[n];
        }
        cache[n] = climbStair(n - 1) + climbStair(n - 2);
        return cache[n];
    }

    public static void main(String[] args) {
        Leetcode70V2 leetcode70 = new Leetcode70V2();
        System.out.println(leetcode70.climbStairs(3));
    }
}
